1. Field of Use
The present improvement relates to apparatus for maintaining information signifying the order of use of a plurality of units and more specifically to error detection means associated with the apparatus.
2. Prior art
In data processing systems having a plurality of units which are used in random sequence, there is a need to share the use of the various units; and to achieve an optimum level of performance, there is a further need to assign for each new use a unit which is least likely to require further utilization by the use currently assigned to the unit.
The preferred embodiment of the present improvement is incorporated in a cache storage system having high speed buffer storage (cache), a directory-look-aside-table (DLAT), and apparatus for maintaining and updating binary coded information related to the order of use of various sections of the buffer storage in accordance with a least recently used (LRU) replacement algorithm.
The cache and its DLAT are divided into a plurality of congruence classes and each congruence class includes a plurality of associativity classes. The LRU apparatus includes storage having one position for each congruence class and storing therein the usage data (LRU binary code) of the associativity classes of the respective congruence class. A description of such cache storage systems is found in many patents and publications, for example, U.S. Pat. No. 3,588,829, entitled, "Integrated Memory System With Block Transfer To A Buffer Store", issued to Boland, et al on June 28, 1971 and assigned to the assignee of the present invention.
During the operation of known cache systems of this type, the LRU binary code for each congruence class is updated with each successful access to (use of) a cache storage (often referred to as a cache line) area corresponding to one of the associativity classes of the congruence class of interest. Depending upon which associativity class is selected for access, certain LRU bits of the binary code must be updated. Remaining bits of the binary code do not require updating because they maintain the history of previous accesses and do not change.
The LRU function in a cache design records the order in which cache lines have been accessed within each congruence class. When a cache congruence class is filled and a cache line load to that congruence class is required, the LRU binary code for the congruence class is used to determine which associativity class in the congruence class has been used least recently. The data in the least recently used cache line is then replaced with the new data. This LRU information is encoded in the binary code associated with each cache congruence class. The number of bits in the binary code is dependent upon the number of associativity classes per congruence class. The function of the LRU demands that the binary code be updated every time an access is made to a congruence class, so that an accurate history of accesses can be maintained.
The LRU function spends the majority of its time recording the order in which cache associativity classes are accessed in each congruence class. When required by a cache miss, the LRU pattern is read from the array, decoded, and used to indicate the least recently used associativity class which then will be replaced with new data. If the LRU array, the update logic or the controls fail, the cache may continue to supply valid data but the error is likely to cause unnecessary line loading which may reduce system performance. The amount of performance degradation depends on the specific failure but may be significant. Thus, early detection of such errors is advantageous.
Because not all LRU bits in an LRU binary code are updated during successful accesses to the cache, known systems have typically read out, from the appropriate LRU storage position, all of the binary code bits, both those requiring update and those that do not. The former bits are updated and all bits, updated and non-updated, are returned to the storage position. This is referred to in the prior art as a READ/MODIFY/WRITE (RMW) cycle for update operations.
It is necessary for acceptable system performance to successfully perform the RMW cycle during a CPU system cycle. As system speeds increase, the RMW cycle places limitations on system cycle times.
To obviate this system limitation, it has been suggested that the LRU storage be implemented with a plurality of individually and separately addressable storage arrays, one for each bit position in the LRU binary code. Separate read/write controls for each array permit a write-only operation by gating off the write controls for those bits which should not be changed.
During each LRU update, only certain of the binary code bit positions of the LRU arrays are written into; no binary code bits are read out for the function of "updating" because the "write only" update function is complete without a READ subcycle. Therefore, no RMW type of operation is required.
To provide error detection, each of the separately addressable arrays includes two bit positions for each congruence class, one for the LRU bit and one for a parity bit. When LRU bits are written into the arrays, an appropriate parity bit is generated and stored with each LRU or modify bit. Parity checking is performed for an LRU binary code when it becomes necessary to transfer data from main storage of the data processing system to the cache line corresponding to the binary code within the pertinent congruence class.
This implementation does present some error detection problems, however. Since the binary code update writes only to selected bits, the unselected bits remain unchanged in the array. Therefore, the entire LRU binary code is not readily available for verification during updates. If checking is omitted during updating, then detection of an LRU binary code error may not occur until much later then the binary code is used to select the least recently used associativity class during a cache line load. Detecting these errors much later than the original time of failure makes determination of the cause of the original error more difficult. The present improvement teaches a method of verifying LRU binary codes immediately after each update to allow detection of errors at the time of failure.
It is therefore a primary object of the present invention to provide an improved error checking method and means.